package first_practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-438-找到字符串中所有字母异位词
 * @date 2025/3/14 15:36
 */
public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        int pLen = p.length();
        int sLen = s.length();
        if (sLen < pLen) return new ArrayList<>();
        int[] pArr = new int[26];
        int[] sArr = new int[26];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < pLen; i++) { // 字母异位词代表每个单词出现的次数一样
            pArr[p.charAt(i) - 97] += 1; // 统计P中每个字母的出现次数
            sArr[s.charAt(i) - 97] += 1; // i与j控制窗口，后续i与j只需要右移一格
        } // 建立滑动窗口
        if (Arrays.equals(sArr, pArr)) ans.add(0);
        for (int i = 1; i < sLen - pLen + 1; i++) {
            int j = i + pLen - 1; // i与j控制窗口，后续i与j只需要右移一格
            sArr[s.charAt(i - 1) - 97] -= 1;
            sArr[s.charAt(j) - 97] += 1;
            if (Arrays.equals(sArr, pArr)) ans.add(i);
        }
        return ans;
    }
}
